package com.cqs.leetcode;

import com.google.common.base.Stopwatch;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.TimeUnit;

/**
 * 动态规划计算
 */
public class UniqueBinarySearchTreesII {

    public List<TreeNode> generateTrees(int n){
        return new Solution().generateTrees(n);
    }

    private List<TreeNode> generateTrees2(int n){
        return new Solution2().generateTrees(n);
    }

    private List<TreeNode> generateTrees3(int n){
        return new Solution3().generateTrees(n);
    }

    // best and quickest
    //Recursive DP -- leetcode
    class Solution{

        public List<TreeNode> generateTrees(int n) {
            return generateTrees(n, 1, n, new List[n][n]);
        }

        /**
         * 当k为根节点的时候 [1,2...,k-1]为结点构成每一棵树均是结点k的左子树
         * [k+1,...,n]为结点构成每一棵树均是结点k的右子树
         * 通过组合出来的就是k为根节点的所有可能的树
         * [1,2...,k-1] k [k+1,...,n]
         * 其中k 的取值范围为[1...n]
         * @param n
         * @param l
         * @param r
         * @param dp
         * @return
         */
        @SuppressWarnings("unchecked")
        private List<TreeNode> generateTrees(int n, int l, int r, List[][] dp) {
            List<TreeNode> res = new ArrayList<>();
            if (l > r) return res;
            if (dp[l-1][r-1] != null) return dp[l-1][r-1];
            for (int i=l; i<=r; i++) {
                List<TreeNode> lefts = generateTrees(n, l, i-1, dp);
                if (lefts.isEmpty()) lefts.add(null);
                List<TreeNode> rights = generateTrees(n, i+1, r, dp);
                if (rights.isEmpty()) rights.add(null);
                //组合
                for (TreeNode ll: lefts) {
                    for (TreeNode rr: rights) {
                        TreeNode t = new TreeNode(i);
                        t.left = ll;
                        t.right = rr;
                        res.add(t);
                    }
                }
            }
            dp[l-1][r-1] = res;
            return res;
        }
    }


    //leetcode
    class  Solution2 {
        public  List<TreeNode> generateTrees(int n) {
            List<TreeNode>[] result = new List[n + 1];
            result[0] = new ArrayList<>();
            if (n == 0) {
                return result[0];
            }

            result[0].add(null);
            for (int len = 1; len <= n; len++) {
                result[len] = new ArrayList<>();
                for (int j = 0; j < len; j++) {
                    for (TreeNode nodeL : result[j]) {
                        for (TreeNode nodeR : result[len - j - 1]) {
                            TreeNode node = new TreeNode(j + 1);
                            node.left = nodeL;
                            node.right = clone(nodeR, j + 1);
                            result[len].add(node);
                        }
                    }
                }
            }
            return result[n];
        }

        private TreeNode clone(TreeNode n, int offset) {
            if (n == null) {
                return null;
            }
            TreeNode node = new TreeNode(n.val + offset);
            node.left = clone(n.left, offset);
            node.right = clone(n.right, offset);
            return node;
        }
    }




    class Solution3{
        /**
         * 动态规划的思路:
         * 在n-1基础上构成的森林上进行构建
         *
         * @param n
         * @return
         */
        public List<TreeNode> generateTrees(int n) {
            List<TreeNode> trees = new ArrayList<>();
            if (n == 0) return trees;
            if (n == 1) {
                TreeNode node = new TreeNode(1);
                trees.add(node);
                return trees;
            }
            trees = generateTrees(1);
            for (int i = 2; i <= n; i++) {
                trees = buildTrees(trees, i);
            }
            return trees;
        }


        //在原来m-1构成的森林的基础上 构建
        private List<TreeNode> buildTrees(List<TreeNode> treeNodes, int m) {
            List<TreeNode> result = new ArrayList<>();
            treeNodes.stream().forEach(treeNode -> {
                result.addAll(addNode(treeNode, m));
            });
            return result;
        }

        /**
         * 在root为根的基础上求树的所有情况
         * 由于是BST树
         * 所以m节点的添加的位置只能是根节点
         * 或者根节点的右孩子(或者root.right 或者 root.right.right ....   root.right.....right)
         * @param root
         * @param m
         * @return
         */
        private List<TreeNode> addNode(final TreeNode root, int m) {
            List<TreeNode> result = new ArrayList<>();
            TreeNode nroot = copyTree(root);
            int time = 0;
            result.add(replace(root, time, m));
            while (nroot != null) {
                result.add(replace(root, ++time, m));
                nroot = nroot.right;
            }
            return result;
        }

        private TreeNode replace(TreeNode root, int time, int m) {
            TreeNode ntree = copyTree(root);
            TreeNode node = ntree;
            TreeNode parent = null;
            while (--time >= 0) {
                parent = node;
                node = node.right;
            }
            TreeNode target = new TreeNode(m);
            if (parent != null) {
                parent.right = target;
            }else {
                ntree = target;
            }
            target.left = node;
            return ntree;
        }


        private TreeNode copyNode(TreeNode node) {
            if (node == null) return null;
            TreeNode copy = new TreeNode(node.val);
            copy.left = node.left;
            copy.right = node.right;
            return copy;
        }

        //middle order copy tree
        private TreeNode copyTree(TreeNode root) {
            final TreeNode croot = copyNode(root);
            TreeNode node = croot;
            Stack<TreeNode> stack = new Stack<>();
            while (node != null || !stack.empty()) {
                if (node != null) {
                    stack.push(node);
                    TreeNode left = copyNode(node.left);
                    node.left = left;
                    node = left;
                } else {
                    TreeNode pop = stack.pop();
                    node = copyNode(pop.right);
                    pop.right = node;
                }
            }
            return croot;
        }
    }


    public static void main(String[] args) {
        int size = 20;
        UniqueBinarySearchTreesII tree = new UniqueBinarySearchTreesII();
        Stopwatch s2 = Stopwatch.createStarted();
        System.out.println(tree.generateTrees(size).size());
        s2.stop();
        System.out.println(s2.elapsed(TimeUnit.MILLISECONDS)+"毫秒");

        Stopwatch s = Stopwatch.createStarted();
        List<TreeNode> treeNodes = tree.generateTrees2(size);
        s.stop();
        System.out.println(s.elapsed(TimeUnit.MILLISECONDS)+"毫秒");
        System.out.println(treeNodes.size());

        Stopwatch s3 = Stopwatch.createStarted();
        System.out.println(tree.generateTrees3(size).size());
        s3.stop();
        System.out.println(s3.elapsed(TimeUnit.MILLISECONDS)+"毫秒");

    }
}
